package com.wxg.algorithm.chapter05;

public class BinarySearch<T extends Comparable> {

    /**
     * 二分查找法, 在有序数组 arr 中, 查找 target
     * 如果找到 target, 返回相应的索引 index
     * 如果没有找到 target, 返回 -1
     *
     * @param arr
     * @param target
     * @return
     */
    public int binarySearch(T[] arr, T target){
        int n = arr.length;

        // 在 arr[l...r] 之中查找 target
        int l = 0, r = n - 1;
        while (l <= r){
//            int mid = (l+r)/2; // 可能产生溢出
            int mid = l + (r-l)/2;
            if( arr[mid].compareTo(target) == 0){
                return mid;
            }

            if ( target.compareTo(arr[mid-1]) < 0 ){
                // 在 arr[l...mid-1] 之中查找 target
                r = mid - 1;
            }else { // target > arr[mid]
                // 在 arr[mid+1...r] 之中查找 target
                l = mid + 1;
            }
        }
        return -1;
    }
}
